Advances in technology have made it possible to do most anything on a mobile phone that can be done on a personal computer. However, since many applications are made for a personal computer, additional processing mechanisms may be necessary to provide the same experience on a mobile phone. Conserving processing power is naturally a concern given the extra tasks and the fact that mobile phones are running on batteries. One way to conserve processing power is to employ a proxy browser. A proxy browser, which may be a server, a computer system or application that acts as an intermediary for requests from clients, such as a mobile phone, seeking resources from other servers. The client connects to the proxy browser and requests a service, such as a file, a connection, a web page, or other resource available from a different server. The proxy browser may then evaluate the request to determine a method to simplify its complexity.
The present invention relates to a proxy browser that is in essence a server that sits between a client browser and the world wide web and takes care of most of the information processing (graphics, layout, JavaScript, and so on) a client browser would do before sending along the information to the client. This is done to conserve processing power on low-end devices as well as for data compression.
The invention specifically relates to one area of the proxy server's function: the laying out of graphical elements specified by a webpage's Hypertext Markup Language (HTML) markup. For example, if the webpage requested by the client contains a table of information, the proxy server will convert that table into a series of lines and text items that will be sent to the client with pre-calculated coordinates for all the associated graphics. The client will then take those coordinates and draw them verbatim to the device screen.
Layout engines in the browser sometimes generate overlapping text, images, and other graphics, especially in a proxy browsing situation, where HTML is converted to primitive paint commands on a server rather than the client device. Because the proxy browsing engine on the server must service thousands of requests per second, brute force detection and correction of overlapping elements (an O(N2) best-case algorithm) is unrealistic. The overlap results in a poor user experience, and may even make some user interactions impossible.
In the prior art, the problem of “given a set of rectangles, find all overlapping pairs” can be solved, but only by a brute force search (i.e., for each rectangle in the set, check every other rectangle for overlap), which runs in O(N2) time. A higher level problem of “given a set of arbitrary polygons, find all overlapping pairs” is more time consuming still, because the O(N2) brute force algorithm is further complicated by needing to use the “rotating calipers” method on each polygon in the set to detect intersection, which runs in time linear to the number of vertices in the polygon. In sum, current methods are too inefficient for real-time use.